#ifndef LIBACCENT_ALGORITHMS_CONCAT_HPP
#define LIBACCENT_ALGORITHMS_CONCAT_HPP

#include "accent/core.hpp"
#include "accent/utility/safe_position.hpp"
#include "accent/utility/tag_functions.hpp"
#include <boost/fusion/container/vector.hpp>
#include <boost/fusion/sequence/intrinsic/at_c.hpp>
#include <boost/fusion/sequence/intrinsic/size.hpp>
#include <boost/fusion/algorithm/iteration/fold.hpp>
#include <boost/mpl/vector.hpp>
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <type_traits>
#include <utility>

namespace accent
{
  namespace detail
  {
    namespace fu = boost::fusion;
    namespace mpl = boost::mpl;

    template <typename Type, typename... Parts>
    struct same_value_type;
    template <typename Type, typename Part, typename... Parts>
    struct same_value_type<Type, Part, Parts...>
      : std::integral_constant<bool,
          std::is_same<Type, decltype(std::declval<Part>().front())>::value &&
          same_value_type<Type, Parts...>::value>
    {};
    template <typename Type>
    struct same_value_type<Type> : std::true_type {};

    template <int I>
    struct int_ { static constexpr int value = I; };

    constexpr inline std::size_t max_s(std::size_t a, std::size_t b) {
      return a < b ? a : b;
    }
    template <typename T>
    constexpr inline std::size_t max_size() { return sizeof(T); }
    template <typename T, typename U, typename... Ts>
    constexpr inline std::size_t max_size() {
      return max_s(sizeof(T), max_size<U, Ts...>());
    }
    template <typename T>
    constexpr inline std::size_t max_align() { return alignof(T); }
    template <typename T, typename U, typename... Ts>
    constexpr inline std::size_t max_align() {
      return max_s(alignof(T), max_align<U, Ts...>());
    }

    template <typename... Types>
    class tagged_variant
    {
      using types = mpl::vector<Types...>;
      static constexpr int size = sizeof...(Types);
      using storage_type = typename std::aligned_storage<max_size<Types...>(),
                                                         max_align<Types...>()>
                                       ::type;
      storage_type storage;
      int tag;

      // no implementation, type deduction only
      auto example() -> typename mpl::at_c<types, 0>::type&;
      auto example() const -> const typename mpl::at_c<types, 0>::type&;

      template <typename F>
      auto invoke_impl(F f, int_<size - 1> i) -> decltype(f(example(), i))
      {
        assert(tag == size - 1);
        return f(at(i), i);
      }
      template <typename F, int I,
                class = typename std::enable_if<I != size - 1>::type>
      auto invoke_impl(F f, int_<I> i) -> decltype(f(example(), i)) {
        return tag == I ? f(at(i), i) : invoke_impl(f, int_<I + 1>());
      }

      template <typename F>
      auto invoke_impl(F f, int_<size - 1> i) const
          -> decltype(f(example(), i)) {
        assert(tag == size - 1);
        return f(at(i), i);
      }
      template <typename F, int I,
                class = typename std::enable_if<I != size - 1>::type>
      auto invoke_impl(F f, int_<I> i) const -> decltype(f(example(), i)) {
        using target = typename mpl::at_c<types, I>::type;
        return tag == I ? f(at(i), i) : invoke_impl(f, int_<I + 1>());
      }

      struct destroy_ {
        template <typename T>
        void operator ()(T& t) const { t.~T(); }
      };

      template <typename F>
      struct wrap_f {
        F f;

        template <typename T, int I>
        auto operator ()(T& t, int_<I>) -> decltype(f(t)) { return f(t); }
      };

    public:
      template <typename F>
      auto invoke_i(F f) -> decltype(f(example(), int_<0>())) {
        assert(tag != -1 && "inactive tagged variant");
        return invoke_impl(f, int_<0>());
      }
      template <typename F>
      auto invoke_i(F f) const -> decltype(f(example(), int_<0>())) {
        assert(tag != -1 && "inactive tagged variant");
        return invoke_impl(f, int_<0>());
      }
      template <typename F>
      auto invoke(F f) -> decltype(f(example())) {
        return invoke_i(wrap_f<F>{f});
      }
      template <typename F>
      auto invoke(F f) const -> decltype(f(example())) {
        return invoke_i(wrap_f<F>{f});
      }

      tagged_variant() : tag(-1) {}
      ~tagged_variant() { if (tag != -1) { invoke(destroy_()); } }
      // FIXME: copy & assign is currently bitwise

      template <int I, typename A>
      void emplace(int_<I>, A a) {
        if (tag != -1) {
          invoke(destroy_());
          tag = -1;
        }
        using target = typename mpl::at_c<types, I>::type;
        new (&storage) target(a);
        tag = I;
      }

      int which() const { return tag; }

      template <int I>
      auto at(int_<I>) -> typename mpl::at_c<types, I>::type& {
        using target = typename mpl::at_c<types, I>::type;
        return reinterpret_cast<target&>(storage);
      }
      template <int I>
      auto at(int_<I>) const -> const typename mpl::at_c<types, I>::type& {
        using target = typename mpl::at_c<types, I>::type;
        return reinterpret_cast<const target&>(storage);
      }
    };

    template <typename Function, typename Sequence>
    auto invoke_at_impl(Sequence& seq, Function f, int i, int_<0> n)
      -> decltype(f(fu::at_c<0>(seq), n))
    {
      assert(i == 0);
      return f(fu::at_c<0>(seq), n);
    }
    template <typename Function, typename Sequence, int I>
    auto invoke_at_impl(Sequence& seq, Function f, int i, int_<I> n)
      -> decltype(f(fu::at_c<0>(seq), n))
    {
      return i == I ? f(fu::at_c<I>(seq), n) :
                      invoke_at_impl(seq, f, i, int_<I - 1>());
    }
    template <typename Function, typename Sequence>
    auto invoke_at(Sequence& seq, Function f, int i)
      -> decltype(f(fu::at_c<0>(seq), int_<0>()))
    {
      using sz = decltype(fu::size(seq));
      return invoke_at_impl(seq, f, i, int_<sz::value - 1>());
    }

    template <typename... Parts>
    class concat_range
    {
      fu::vector<Parts...> parts;
      int current_front;
      int current_back;

      static constexpr int num_parts = sizeof...(Parts);
      typedef decltype(fu::at_c<0>(parts).front()) reference;

      struct empty_ {
        template <typename R, int I>
        bool operator ()(const R& r, int_<I>) const { return r.empty(); }
      };
      struct pop_front_ {
        template <typename R, int I>
        void operator ()(R& r, int_<I>) const { r.pop_front(); }
      };
      struct front_ {
        template <typename R, int I>
        reference operator ()(const R& r, int_<I>) const { return r.front(); }
      };
      struct pop_back_ {
        template <typename R, int I>
        void operator ()(R& r, int_<I>) const { r.pop_back(); }
      };
      struct back_ {
        template <typename R, int I>
        reference operator ()(const R& r, int_<I>) const { return r.back(); }
      };

      template <typename Function>
      auto invoke_at_front(Function f)
        -> decltype(invoke_at(parts, f, current_front))
      {
        return invoke_at(parts, f, current_front);
      }
      template <typename Function>
      auto invoke_at_front(Function f) const
        -> decltype(invoke_at(parts, f, current_front))
      {
        return invoke_at(parts, f, current_front);
      }

      template <typename Function>
      auto invoke_at_back(Function f)
        -> decltype(invoke_at(parts, f, current_back))
      {
        return invoke_at(parts, f, current_back);
      }
      template <typename Function>
      auto invoke_at_back(Function f) const
        -> decltype(invoke_at(parts, f, current_back))
      {
        return invoke_at(parts, f, current_back);
      }

      void find_next(int& current) const {
        while (current <= current_back && invoke_at(parts, empty_(), current))
          ++current;
      }
      void next() { find_next(current_front); }
      void prev() {
        while (current_back >= current_front && invoke_at_back(empty_()))
          --current_back;
      }

    public:
      using traversal = support::minimum_tag<typename Parts::traversal...>;

      concat_range(Parts... parts)
        : parts(std::move(parts)...),
          current_front(0),
          current_back(num_parts - 1)
      {
        next();
        prev();
      }

      bool empty() const {
        return current_front > current_back || invoke_at_front(empty_());
      }
      void pop_front() {
        invoke_at_front(pop_front_());
        next();
      }
      reference front() const {
        return invoke_at_front(front_());
      }

      class position
      {
        using holder = tagged_variant<support::safe_position<Parts>...>;
        holder wrapped;
        friend class concat_range;

        int index() const { return wrapped.which(); }

        struct deref {
          template <typename P>
          reference operator ()(const P& p) const {
            return *p;
          }
        };

        struct equals {
          const holder& rhs;

          template <typename P, int I>
          bool operator ()(const P& p, int_<I> i) const {
            return p == rhs.at(i);
          }
        };

        template <typename R>
        struct apply_until {
          R& r;

          template <typename P>
          void operator ()(const P& p) const {
            r = r.until(p);
          }
        };
        struct until {
          position& p;

          template <typename R, int I>
          void operator ()(R& r, int_<I>) const {
            p.wrapped.invoke(apply_until<R>{r});
          }
        };

        template <typename R>
        struct apply_from {
          R& r;

          template <typename P>
          void operator ()(const P& p) const {
            r = r.from(p);
          }
        };
        struct from {
          position& p;

          template <typename R, int I>
          void operator ()(R& r, int_<I>) const {
            p.wrapped.invoke(apply_from<R>{r});
          }
        };

      public:
        position() {}

        template <typename P, int I>
        position(int_<I> i, P p) { wrapped.emplace(i, p); }

        explicit operator bool() const { return index() != -1; }
        bool operator !() const { return index() == -1; }
        reference operator *() const { return wrapped.invoke(deref()); }
        friend bool operator ==(const position& lhs, const position& rhs) {
          return lhs.index() == rhs.index() &&
                 lhs.wrapped.invoke_i(equals{rhs.wrapped});
        }
      };

    private:
      struct front_position_ {
        template <typename R, int I>
        position operator ()(const R& r, int_<I> i) const {
          return position(i, r.front_position());
        }
      };
      struct back_position_ {
        template <typename R, int I>
        position operator ()(const R& r, int_<I> i) const {
          return position(i, r.back_position());
        }
      };

    public:
      position front_position() const {
        return invoke_at_front(front_position_());
      }

      concat_range until(position p) const {
        concat_range r = *this;
        r.current_back = p.index();
        r.invoke_at_back(typename position::until{p});
        r.prev();
        return r;
      }

      concat_range from(position p) const {
        concat_range r = *this;
        r.current_front = p.index();
        r.invoke_at_front(typename position::from{p});
        r.next();
        return r;
      }

      position back_position() const {
        return invoke_at_back(back_position_());
      }
      reference back() const { return invoke_at_back(back_()); }
      void pop_back() {
        invoke_at_back(pop_back_());
        prev();
      }

    private:
      struct add_sizes {
        int front, back, current;

        typedef std::size_t result_type;
        template <typename R>
        std::size_t operator ()(std::size_t a, const R& r) {
          bool in_bounds = current >= front && current <= back;
          ++current;
          return in_bounds ? a + r.size() : a;
        }
      };

      struct size_ {
        template <typename R, int I>
        std::size_t operator ()(const R& r, int_<I>) const {
          return r.size();
        }
      };
      struct skip_front_ {
        std::size_t n;
        template <typename R, int I>
        void operator ()(R& r, int_<I>) const {
          r.skip_front(n);
        }
      };
      struct skip_back_ {
        std::size_t n;
        template <typename R, int I>
        void operator ()(R& r, int_<I>) const {
          r.skip_back(n);
        }
      };
      struct index {
        std::size_t n;
        template <typename R, int I>
        reference operator ()(R& r, int_<I>) const {
          return r[n];
        }
      };

    public:
      std::size_t size() const {
        return fu::fold(parts, static_cast<std::size_t>(0),
          add_sizes{current_front, current_back});
      }

      void skip_front(std::size_t n) {
        while (n > 0) {
          auto available = invoke_at_front(size_());
          auto actual = std::min(n, available);
          invoke_at_front(skip_front_{actual});
          n -= actual;
          next();
        }
      }

      void skip_back(std::size_t n) {
        while (n > 0) {
          auto available = invoke_at_back(size_());
          auto actual = std::min(n, available);
          invoke_at_back(skip_back_{actual});
          n -= actual;
          prev();
        }
      }

      reference operator [](std::size_t n) const {
        int current = current_front;
        auto available = invoke_at(parts, size_(), current);
        while (n >= available) {
          n -= available;
          ++current;
          find_next(current);
        }
        return invoke_at(parts, index{n}, current);
      }
    };
  }

  template <typename Part, typename... Parts>
  detail::concat_range<Part, Parts...> concat(Part part, Parts... parts)
  {
    // FIXME: Use SFINAE to avoid instantiation of invalid concat_ranges.
    static_assert(
      detail::same_value_type<decltype(part.front()), Parts...>::value,
      "Concatenated ranges must have same value type.");
    return { std::move(part), std::move(parts)... };
  }
}

#endif
